package com.example.demo.leetcode.top;

public class CommonPartnerTest {



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //后序遍历，从下往上
        /**
         * 1.null 直接返回
         * 2.遇到目标节点，直接返回root
         * 遍历左右子树
         * 3.子树一边为null，说明没有遍历到，直接返回另一边
         * 4.最后返回root
         */
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }


    public static void main(String[] args) {



    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


}
